Contrôle de type on-policy par approximations

3. Contrôle semi-gradient sur des tâches continues

3.8. Algorithme différentiel semi-gradient Sarsa n-step

Nous pouvons pour terminer construire l'algorithme de la version Sarsa n-step en construisant la revenu moyen différentiel appliqué à ce cas :

$${G_{t:t + n}} = \left( {{R_{t + 1}} + {R_{t + 2}} + ... + {R_{t + n}}} \right) - n\overline {{R_{t + n - 1}}} + \hat q\left( {{S_{t + n}},{A_{t + n}},{\textbf{w}_{t + n - 1}}} \right)$$

où $\overline R$ est l'estimation de $r(\pi)$ pour $n \ge 1$ et $t+n < T$. Si $t+n \ge T$ alors on définit ${G_{t:t + n}}=G_t$.

Dans ce cas, l'erreur TD devient donc :

$${\delta _t} = {G_{t:t + n}} - \hat q\left( {{S_t},{A_t},\textbf{w}} \right)$$

Une version de l'algorithme serait donc la suivante :

3.9. Amélioration de l'algorithme différentiel

Dans l'algorithme précédent, le pas de calcul utilisé pour la mise à jour du revenu moyen différentiel $β$ doit être très petit afin que $\overline R$ devienne une bonne estimation du le long terme du revenu moyen. Malheureusement, $\overline R$ va être biaisé par ses valeurs initiales sur de nombreux pas de calculs, ce qui peut rendre l'apprentissage moins performant.

On peut imaginer l'idée de calculer une moyenne sur un échantillonnage des récompenses pour obtenir $\overline R$. Cela aura pour effet d'initialiser $\overline R$ rapidement mais sur le long terme de le mettre à jour lentement. Comme la stratégie change lentement, $\overline R$ changera également et cette non stationnarité sur le long terme n'est pas en faveur de cette méthode.

La solution est de mettre à jour le pas de calcul $β$ à chaque pas de temps en le faisant décroitre en suivant une relation de type :

$$\left\{ \begin{array}{l} {\beta _t} \leftarrow \frac{{{\beta _0}}}{{{o_t}}}\\ {o_t} \leftarrow {o_{t - 1}} + \beta_0 \left( {1 - {o_{t - 1}}} \right) \end{array} \right. \quad avec \quad o_{0}=0$$